在分布式系统中，由于有多个机器（进程）在一起协调工作，于是如何定义分布式系统中事件的先后顺序就成了难题，本文介绍论文 《Time, Clocks, and the Ordering of Events in a Distributed System》中提到的Lamport时钟。
什么是逻辑时钟
逻辑时钟是为了解决分布式系统中事件顺序问题而提出的概念。与物理时钟不同，逻辑时钟不依赖于实际时间，而是通过节点间的交互来确定事件的先后顺序。
分布式系统中定义一个事件的先后顺序是一个难点，下意识的第一反应是：给每个事件加上一个物理的时间戳，不就可以比较不同事件的时间戳来决定其顺序了吗？
这样做的问题在于：在分布式系统中，由多个机器组合起来协调工作，而每个机器上的物理时间也不尽相同，所以“物理时间戳”本质上是一个机器属性，并不一定系统中所有机器都满足同一个时间度量。
在分布式系统中，事件的顺序难以直接通过物理时间戳确定，因为不同机器的物理时间可能不一致，而且如果两个节点不交互，它们的时间无需同步。逻辑时钟通过节点间的交互，确保事件顺序的一致性，而不依赖于物理时间。它关注的是事件的因果关系，而非实际时间。物理时间戳的局限性在于它依赖于本地机器时间，不同机器的时间可能不一致，因此在分布式系统中，物理时间戳无法全局一致地衡量事件顺序。逻辑时钟的核心在于通过节点交互确定事件顺序，而非依赖物理时间。它解决了分布式系统中事件顺序的难题，避免了物理时钟不同步带来的问题。
时序关系与相对论
通过前面的讨论我们知道通过物理时钟（即绝对参考系)来区分先后顺序的前提是所有节点的时钟完全同步，但目前并不现实。因此，在没有绝对参考系的情况下，在一个分布式系统中，你无法判断事件A是否发生在事件B之前，除非A和B存在某种依赖关系，即分布式系统中的事件仅仅是部分有序的。
上面的结论跟狭义相对论有异曲同工之妙，在狭义相对论中，不同观察者在同一参考系中观察到的事件先后顺序是一致的，但是在不同的观察者在不同的参考系中对两个事件谁先发生可能具有不同的看法. 当且仅当事件A是由事件B引起的时候, 事件A和B之间才存在一个先后关系。两个事件可以建立因果关系的前提是：两个事件之间可以用等于或小于光速的速度传递信息。 值得注意的是这里的因果关系指的是时序关系，即时间的前后，并不是逻辑上的原因和结果。
那么是否我们可以参考狭义相对论来定义分布式系统中两个事件的时序呢？在分布式系统中，网络是不可靠的，所以我们去掉可以和速度的约束，可以得到两个事件可以建立因果（时序）关系的前提是：两个事件之间是否发生过信息传递。在分布式系统中，进程间通信、消息发送等都属于信息传递，如果两个进程间没有任何交互，实际上他们之间内部事件的时序也无关紧要。但是有交互的情况下，特别是多个节点的要保持同一副本的情况下，事件的时序非常重要。
happen-before关系
一个分布式系统中的事件，在很多情况（只是很多情况下，并没有全部，下面会展开讨论）下都能定义其先后顺序了，在论文中，lamport将这个关系定义为happen-before关系：
- 引入符号→→做为表示事件之间
happen-before的记号。 - 在同一个进程中，如果事件aa在事件bb之前发生，那么a→ba→b。（这是因为根据规则1，进程每次发出事件之后都会将本地的lamport时钟加一，于是可以在同一个进程内定义事件的先后顺序了）
- 在不同的进程中，如果事件aa表示一个进程发出一个事件，事件bb表示接收进程收到这个事件，那么也必然满足a→ba→b。（这是因为根据规则2，接收进程在收到事件之后会取本地时钟和事件时钟的最大值并且+1，于是发出事件和接收事件尽管在不同的进程，但是也可以比较其lamport时钟知道其先后顺序了）
- 最后，
happend-before关系是满足传递性的，即：如果a→ba→b且b→cb→c，那么也一定有a→ca→c。
讲到了这里，似乎已经明白了lamport时钟要解决的问题，以及分布式系统中事件之间happend-before关系的定义。但是还有疑点没有解开：
- 一个分布式系统中的事件是否都满足
happen-before关系？按照前面全序、偏序关系的定义，这个问题相当于问：happen-before关系是全序还是偏序关系？（全序、偏序）
这两个问题可以放在一起解答：分布式系统中的所有事件并不都满足happen-before关系，按照前面全序、偏序关系的定义，由于这个集合中并不是所有情况下都满足这种关系，所以说happen-before关系是一种偏序关系。
以下图来看看：
（引用自Lamport Clocks - Kevin Sookocheff）
这个系统的工作方式，在前面解释规则1、2的时候已经有说明，在这里就不再阐述。可以注意到P3P3进程和P2P2进程都有一个时间2，在这个时间上这两个进程做了两个不同的事件：
- 从进程P3P3的视角来看：时间2发出事件给进程P2P2，按照算法最后进程P2P2计算出来收到这个事件的时间为5。
- 从进程P2P2的视角来看，在本进程上时间2也在时间5之前。
所以无论如何，这两个进程上在时间2上发生的事件都不能比较先后顺序了。
如果分布式系统中的两个事件，不满足happen-before关系，在论文中称这两个事件为“并行事件（concurrent event）”。
现实的系统中，确实存在很多并行事件。比如向一个KV系统中同时写入两个并无关联的数据，由于无法根据Lamport时钟对比出先后来，这些操作就可以认为是并行的。
Lamport 逻辑时钟
分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。注意：以下文章中提及的时间戳如无特别说明，都指的是Lamport 逻辑时钟的时间戳，不是物理时钟的时间戳
逻辑时钟定义
Clock Condition.对于任意事件a, b：如果a -> b（->表示a先于b发生），那么C(a) < C(b), 反之不然, 因为有可能是并发事件 C1.如果a和b都是进程Pi里的事件，并且a在b之前，那么Ci(a) < Ci(b) C2.如果a是进程Pi里关于某消息的发送事件，b是另一进程Pj里关于该消息的接收事件，那么Ci(a) < Cj(b)
Lamport 逻辑时钟原理如下：
- 每个事件对应一个Lamport时间戳，初始值为0
- 如果事件在节点内发生，本地进程中的时间戳加1
- 如果事件属于发送事件，本地进程中的时间戳加1并在消息中带上该时间戳
- 如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1
假设有事件a、b，C(a)、C(b)分别表示事件a、b对应的Lamport时间戳，如果a发生在b之前(happened before)，记作 a -> b，则有C(a) < C(b)，例如图1中有 C1 -> B1，那么 C(C1) < C(B1)。通过该定义，事件集中Lamport时间戳不等的事件可进行比较，我们获得事件的偏序关系(partial order)。注意：如果C(a) < C(b)，并不能说明a -> b，也就是说C(a) < C(b)是a -> b的必要不充分条件
如果C(a) = C(b)，那a、b事件的顺序又是怎样的？值得注意的是当C(a) = C(b)的时候，它们肯定不是因果关系，所以它们之间的先后其实并不会影响结果，我们这里只需要给出一种确定的方式来定义它们之间的先后就能得到全序关系。注意：Lamport逻辑时钟只保证因果关系（偏序）的正确性，不保证绝对时序的正确性。
一种可行的方式是利用给进程编号，利用进程编号的大小来排序。假设a、b分别在节点P、Q上发生，Pi、Qj分别表示我们给P、Q的编号，如果 C(a) = C(b) 并且 Pi < Qj，同样定义为a发生在b之前，记作 a => b（全序关系）。假如我们对图1的A、B、C分别编号Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 并且 Bj < Ck，则 B4 => C3。
通过以上定义，我们可以对所有事件排序，获得事件的全序关系(total order)。上图例子，我们可以进行排序：C1 => B1 => B2 => A1 => B3 => A2 => C2 => B4 => C3 => A3 => B5 => C4 => C5 => A4
观察上面的全序关系你可以发现，从时间轴来看B5是早于A3发生的，但是在全序关系里面我们根据上面的定义给出的却是A3早于B5，可以发现Lamport逻辑时钟是一个正确的算法，即有因果关系的事件时序不会错，但并不是一个公平的算法，即没有因果关系的事件时序不一定符合实际情况。
如何使用逻辑时钟解决分布式锁问题
上面的分析过于理论，下面我们来尝试使用逻辑时钟来解决分布式锁问题。
分布式锁问题本质上是对于共享资源的抢占问题，我们先对问题进行定义：
- 已经获得资源授权的进程，必须在资源分配给其他进程之前释放掉它；
- 资源请求必须按照请求发生的顺序进行授权；
- 在获得资源授权的所有进程最终释放资源后，所有的资源请求必须都已经被授权了。
首先我们假设，**对于任意的两个进程Pi和Pj，它们之间传递的消息是按照发送顺序被接收到的, 并且所有的消息最终都会被接收到。每个进程会维护一个它自己的对其他所有进程都不可见的请求队列。我们假设该请求队列初始时刻只有一个消息（T0:P0）资源请求，P0代表初始时刻获得资源授权的那个进程，T0小于任意时钟初始值
- 为请求该项资源，进程Pi发送一个（Tm:Pi）资源请求（请求锁）消息给其他所有进程，并将该消息放入自己的请求队列，在这里Tm代表了消息的时间戳
- 当进程Pj收到（Tm:Pi）资源请求消息后，将它放到自己的请求队列中，并发送一个带时间戳的确认消息给Pi。(注：如果Pj已经发送了一个时间戳大于Tm的消息，那就可以不发送)
- 释放该项资源（释放锁）时，进程Pi从自己的消息队列中删除所有的（Tm:Pi）资源请求，同时给其他所有进程发送一个带有时间戳的Pi资源释放消息
- 当进程Pj收到Pi资源释放消息后，它就从自己的消息队列中删除所有的（Tm:Pi）资源请求
- 当同时满足如下两个条件时，就将资源分配（锁占用）给进程Pi：
- 按照全序关系排序后，（Tm:Pi）资源请求排在它的请求队列的最前面
- i已经从所有其他进程都收到了时间戳>Tm的消息
下面我会用图例来说明上面算法运作的过程，假设我们有3个进程，根据算法说明，初始化状态各个进程队列里面都是(0:0)状态，此时锁属于P0。
接下来P1会发出请求资源的消息给所有其他进程，并且放到自己的请求队列里面，根据逻辑时钟算法，P1的时钟走到1，而接受消息的P0和P2的时钟为消息时间戳+1。
收到P1的请求之后，P0和P2要发送确认消息给P1表示自己收到了。注意，由于目前请求队列里面第一个不是P1发出的请求，所以此时锁仍属于P0。但是由于收到了确认消息，此时P1已经满足了获取资源的第一个条件：P1已经收到了其他所有进程时间戳大于1的消息。
假设P0此时释放了锁（这里为了方便演示做了这个假设，实际上P0什么时候释放资源都可以，算法都是正确的，读者可自行推导），发送释放资源的消息给P1和P2，P1和P2收到消息之后把请求(0:0)从队列里面删除。
当P0释放了资源之后，我们发现P1满足了获取资源的两个条件：它的请求在队列最前面；P1已经收到了其他所有进程时间戳大于1的消息。也就是说此时P1就获取到了锁。
值得注意的是，这个算法并不是容错的，有一个进程挂了整个系统就挂了，因为需要等待所有其他进程的响应，同时对网络的要求也很高。
Reference:Time, Clocks, and the Ordering of Events in a Distributed System
YJ